package Hot100.Medium.Backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LC22_GeneParenthesis {
    List<String> result = new ArrayList<>();
    StringBuilder path = new StringBuilder();

    public List<String> generateParenthesis(int n) {
        if (n == 0) return result;
        backtrack(n, 0, 0);
        return result;
    }

    // leftCount: 已使用的左括号数量
    // rightCount: 已使用的右括号数量
    public void backtrack(int n, int leftCount, int rightCount) {
        // 当路径长度达到2*n时，说明已生成完整的括号组合
        if (path.length() == 2 * n) {
            result.add(path.toString());
            return;
        }

        // 选择1：添加左括号（前提是左括号还有剩余）
        if (leftCount < n) {
            path.append('(');
            backtrack(n, leftCount + 1, rightCount);
            path.deleteCharAt(path.length() - 1);
        }

        // 选择2：添加右括号（前提是右括号数量小于左括号数量）
        if (rightCount < leftCount) {
            path.append(')');
            backtrack(n, leftCount, rightCount + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
